#!/usr/bin/env python
# -*- coding: utf-8 -*-
# @Time    : 2020/6/18 15:27
# @USER    : Shengji He
# @File    : RecoverTreePreorderTraversal.py
# @Software: PyCharm
# @Version  : Python-
# @TASK:


# Definition for a binary tree node.
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None


class Solution:
    def recoverFromPreorder(self, S: str) -> TreeNode:
        """
        We run a preorder depth first search on the root of a binary tree.

        At each node in this traversal, we output D dashes (where D is the depth of this node), then we output the
        value of this node.  (If the depth of a node is D, the depth of its immediate child is D+1.
        The depth of the root node is 0.)

        If a node has only one child, that child is guaranteed to be the left child.

        Given the output S of this traversal, recover the tree and return its root.

        Note:
            - The number of nodes in the original tree is between 1 and 1000.
            - Each node will have a value between 1 and 10^9.

        :param S: str
        :return: TreeNode

        """
        path, pos = [], 0
        while pos < len(S):
            level = 0
            while S[pos] == '-':
                level += 1
                pos += 1
            value = 0
            while pos < len(S) and S[pos].isdigit():
                value = value * 10 + (ord(S[pos]) - ord('0'))
                pos += 1
            node = TreeNode(value)
            if level == len(path):
                if path:
                    path[-1].left = node
            else:
                path = path[:level]
                path[-1].right = node
            path.append(node)
        return path[0]


if __name__ == '__main__':
    S = Solution()
    print(S.recoverFromPreorder("1-2--3--4-5--6--7"))
    print('done')
